package 力扣.树.层序遍历;

import java.util.*;

public class 二叉树的层序遍历II_107 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);

        TreeNode root21 = new TreeNode(9);
        TreeNode root22 = new TreeNode(20);

        TreeNode root31 = new TreeNode(15);
        TreeNode root32 = new TreeNode(7);

        root.left = root21;
        root.right = root22;
        root22.left = root31;
        root22.right = root32;

        List<List<Integer>> lists = levelOrderBottom(root);
        System.out.println(lists);
    }
    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root != null){
            deque.offerFirst(root);
        }
        while (deque.size() > 0){
            final int size = deque.size();
            List<Integer> teList = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode teTree = deque.pollLast();
                assert teTree != null;
                teList.add(teTree.val);
                if (teTree.left != null){
                    deque.offerFirst(teTree.left);
                }
                if (teTree.right != null){
                    deque.offerFirst(teTree.right);
                }
            }
//            ans.add(teList);
            ans.add(0,teList);
        }
//        Collections.reverse(ans);
        return ans;
    }
}
